import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

//Preprocess the text file, replace any reference to a character class in a token with the values from the character class (like a macro)
//Replace expr+ with (expr (expr)*)
public class NFA{
	
	public Node start, finish;
	public String name;
	
	public static final char EPS_CHAR = 949;
	public static final char[] EPS = {EPS_CHAR}; //epsilon
	public static final char[] fullRange = new char[128]; //@TODO: only need 32-126 for printable ASCII
	
	static {
		for (int i = 0; i < fullRange.length; i++){
			fullRange[i] = (char)i;
		}
	}
	
	public NFA(Node start, Node finish){
		this(start, finish, "");
	}
	
	public NFA(Node start, Node finish, String name){
		this.start = start;
		this.finish = finish;
		this.name = name;
	}
	
	//public char[] range;
	
	public static NFA makeRange(NFA r1, NFA r2, String tokenName){
		Set<Character> key1 = r1.start.adjList.keySet();
		Set<Character> key2 = r2.start.adjList.keySet();
		char c1 = 0, c2 = 0;
		for (char c : key1){
			c1 = c;
			break;
		}
		for (char c : key2){
			c2 = c;
			break;
		}
		return new NFA(NFA.makeRange(c1, c2), tokenName);
	}

	//I only need a constructor that takes a char, it will accept strings of that character by itself only.
	//PAlso the empty string is denoted as Character.toChars(145)[0].
	public NFA(char input, String tokenName){
		this(new char[] {input}, tokenName);
	}

	//this needs to be the trivial NFA. 
	public NFA(){
		 
	}
	
	public NFA(char[] range, String tokenName){
		this(range, false, fullRange, tokenName);
	}
	
	public NFA(char[] range, boolean negated, char[] inRange, String tokenName){
		start = new Node(false);
		start.tokenName = tokenName;
		finish = new Node(true);
		finish.tokenName = tokenName;
		char[] newrange;
		
		//Figure out what transitions we need
		if (!negated){
			newrange = range;
		}
		else{
			int[] temp = new int[inRange.length];
			for (int i = 0; i < temp.length; i++){
				temp[i] = i;
			}
			for (int i = 0; i < range.length; i++){
				temp[(int)range[i]] = -1;
			}
			ArrayList<Character> toAdd = new ArrayList<Character>(256);
			for (int i = 0; i < temp.length; i++){
				if (temp[i] != -1){
					toAdd.add((Character)((char)temp[i]));
				}
			}
			newrange = new char[toAdd.size()];
			for (int i = 0; i < toAdd.size(); i++){
				newrange[i] = toAdd.get(i);
			}
		}
		
		start.addTransitions(newrange, finish);
	}
	
	
	public static char[] rangeOr(char[] range1, char[] range2){
		char[] ret = new char[range1.length + range2.length];
		for (int i = 0; i < range1.length; i++){
			ret[i] = range1[i];
		}
		for (int i = 0; i < range2.length; i++){
			ret[i+range1.length] = range2[i];
		}
		return ret;
	}
	
	public static char[] makeRange(char start, char end){
		if (end < start){// return new char[0];
			System.err.println("Invalid range: " + start + "-" + end + ".");
			return null;
		}
		
		char[] ret = new char[end-start+1];
		for (char c = start; c <= end; c++){
			ret[(int)(c - start)] = c;
		}
		return ret;
	}
	
	/*public NFA clone(){
		NFA ret = new NFA();
		//ret.start = 
		return null;
	}*/

	public static NFA concatenate(NFA rg1, NFA rg2, String tokenName){
		//rg1 = rg1.clone();
		//rg2 = rg2.clone();
		Node newstart = rg1.start;
		newstart.accepting = false;
		newstart.tokenName = tokenName;
		rg1.finish.addTransitions(EPS, rg2.start);
		rg1.finish.accepting = false;
		Node newfinish = new Node(true);
		newfinish.tokenName = tokenName;
		rg2.finish.addTransitions(EPS, newfinish);
		rg2.finish.accepting = false;
		return new NFA(newstart, newfinish);
	}
	
	public static NFA union(NFA rg1, NFA rg2, String tokenName){
		//rg1 = rg1.clone();
		//rg2 = rg2.clone();
		Node newstart = new Node();
		newstart.accepting = false;
		newstart.tokenName = tokenName;
		newstart.addTransitions(EPS, rg1.start);
		newstart.addTransitions(EPS, rg2.start);
		Node newfinish = new Node(true);
		newfinish.tokenName = tokenName;
		rg2.finish.addTransitions(EPS, newfinish);
		rg2.finish.accepting = false;
		rg1.finish.addTransitions(EPS, newfinish);
		rg1.finish.accepting = false;
		return new NFA(newstart, newfinish);
	}
	
	public static NFA star(NFA rg, String tokenName){
		//rg = rg.clone();
		Node newstart = new Node();
		newstart.accepting = false;
		newstart.tokenName = tokenName;
		Node newfinish = new Node(true);
		newfinish.tokenName = tokenName;
		newstart.addTransitions(EPS, rg.start);
		newstart.addTransitions(EPS, newfinish);
		rg.finish.addTransitions(EPS, newfinish);
		rg.finish.addTransitions(EPS, rg.start);
		rg.finish.accepting = false;
		return new NFA(newstart, newfinish);
	}

	
	public String toString(Node curnode, String tabs){
		//Get all possible transitions
		HashMap<Character, ArrayList<Node>> adjList = curnode.adjList;
		Character[] transitions = adjList.keySet().toArray(new Character[0]);
		String ret = "";
		//Put target nodes in a 
		Set<Node> nodes = new HashSet<Node>();
		ArrayList<Node> curtargets;
		for (int i = 0; i < transitions.length; i++){
			curtargets = curnode.adjList.get(transitions[i]);
			for (int j = 0; j < curtargets.size(); j++){
				nodes.add(curtargets.get(j));
			}
		}
		
		for (Node n : nodes){
			ret += "Node: " + n.name + ": " + n.toString() + "\n" + tabs + toString(n, tabs + "\t");
		}
		return ret;
	}
	
	public String toString(){
		return toString(start, "");
	}

	
	
}
